package org.common.utils.geometry;
import java.util.ArrayList;
import java.util.List;

/**
 * 几何工具
 */
public class GeometryUtil {
	/**
	 * 判断点是否在多边形内
	 * @param point 检测点
	 * @param pts   多边形的顶点
	 * @return 点在多边形内返回true,否则返回false
	 */
	public static boolean isInPtInPoly(Point point, List<Point> pts) {
		int N = pts.size();
		boolean boundOrVertex = true; // 如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
		int intersectCount = 0;// cross points count of x
		double precision = 2e-10; // 浮点类型计算时候与0比较时候的容差
		Point p1, p2;// neighbour bound vertices
		Point p = point; // 当前点

		p1 = pts.get(0);// left vertex
		for (int i = 1; i <= N; ++i) {// check all rays
			if (p.equals(p1)) {
				return boundOrVertex;// p is an vertex
			}

			p2 = pts.get(i % N);// right vertex
			if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {// ray is outside of our interests
				p1 = p2;
				continue;// next ray left point
			}

			if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {// ray is crossing over by the algorithm
																			// (common part of)
				if (p.y <= Math.max(p1.y, p2.y)) {// x is before of ray
					if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {// overlies on a horizontal ray
						return boundOrVertex;
					}

					if (p1.y == p2.y) {// ray is vertical
						if (p1.y == p.y) {// overlies on a vertical ray
							return boundOrVertex;
						} else {// before ray
							++intersectCount;
						}
					} else {// cross point on the left side
						double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;// cross point of y
						if (Math.abs(p.y - xinters) < precision) {// overlies on a ray
							return boundOrVertex;
						}

						if (p.y < xinters) {// before ray
							++intersectCount;
						}
					}
				}
			} else {// special case when ray is crossing through the vertex
				if (p.x == p2.x && p.y <= p2.y) {// p crossing over p2
					Point p3 = pts.get((i + 1) % N); // next vertex
					if (p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)) {// p.x lies between p1.x & p3.x
						++intersectCount;
					} else {
						intersectCount += 2;
					}
				}
			}
			p1 = p2;// next ray left point
		}

		if (intersectCount % 2 == 0) {// 偶数在多边形外
			return false;
		} else { // 奇数在多边形内
			return true;
		}
	}

	/**
	 * 判断是否在圆形内
	 * @param p 任意点
	 * @param c 圆
	 * @return
	 */
	public static byte isInCircle(Point p, Circle c) {// 判断点与圆心之间的距离和圆半径的关系
		double d2 = Math.hypot((p.getX() - c.getCC().getX()), (p.getY() - c.getCC().getY()));
		double r = c.getR();
		if (d2 > r) // 圆外
			return 1;
		else if (d2 < r) // 圆内
			return -1;
		else
			return 0; // 圆上
	}

	/**
	 * 根据两点计算出角度
	 * @param from   来源点
	 * @param target 目标点
	 * @return 返回角度值
	 */
	public static float getAngle(Point from, Point target) {
		float angle = (float) Math.toDegrees(Math.atan2(target.getY() - from.getY(), target.getX() - from.getX()));
		if (angle < 0)
			angle += 360;
		return angle;
	}
	
	/**
	 * 根据角度换算孤度
	 * @param angle  角度
	 * @return 返回孤度值
	 */
	public static double toRadians(float angle) 
	{
		return Math.toRadians(angle);
	}
	
	
	/**
	 * 根据a、b两点，获取对应延长坐标点。
	 * @param a a点
	 * @param b b点
	 * @param length 延长距离
	 * @return 返回对应延长距离点对象
	 */
	public static Point getProlongPoint(Point a , Point b , int length) {
		float angle = GeometryUtil.getAngle(a , b);
		double radians = Math.toRadians(angle);
		float newX = b.getX() + (int)(Math.cos(radians) * length);
		float newY = b.getY() + (int)(Math.sin(radians) * length);
		return new Point(newX, newY);
	}
	
	
	/**
	 * 判断是否在扇形内
	 * @param fromPoint     来源点
	 * @param targetPoint   目标点
	 * @param angle	角度范围
	 * @return 返回target目标点是否在扇形角度范围内
	 */
	public static boolean isInSector(Point fromPoint, Point selectPoint , Point targetPoint , float angle) {
		angle /= 2;
		//选择点角度
		float selectPointAngle = GeometryUtil.getAngle(fromPoint, selectPoint);
		//目标点角度
    	float targetPointAngle = GeometryUtil.getAngle(fromPoint, targetPoint);
    	int inSectorAngle = (int)Math.abs(targetPointAngle - selectPointAngle);
    	return inSectorAngle < angle;
    }
	
	/**
	 * @param line1	线条1对象
	 * @param line2	线条2对象
	 * @return 返回是否两条线相交
	 */
	public static boolean isLineIntersectionLine(Line line1, Line line2) {
		double l1x1 = line1.getLeftTop().getX();
		double l1y1 = line1.getLeftTop().getY();
		double l1x2 = line1.getRightBottom().getX();
		double l1y2 = line1.getRightBottom().getY();
		
		double l2x1 = line2.getLeftTop().getX();    
		double l2y1 = line2.getLeftTop().getY();    
		double l2x2 = line2.getRightBottom().getX();
		double l2y2 = line2.getRightBottom().getY();
		
		return java.awt.geom.Line2D.linesIntersect(l1x1, l1y1, l1x2, l1y2, l2x1, l2y1, l2x2, l2y2);
		
//        // 快速排斥实验 首先判断两条线段在 x 以及 y 坐标的投影是否有重合。 有一个为真，则代表两线段必不可交。
//        if (Math.max(l1x1,l1x2) < Math.min(l2x1 ,l2x2)
//            || Math.max(l1y1,l1y2) < Math.min(l2y1,l2y2)
//            || Math.max(l2x1,l2x2) < Math.min(l1x1,l1x2)
//            || Math.max(l2y1,l2y2) < Math.min(l1y1,l1y2))
//        {
//            return false;
//        }
//        // 跨立实验  如果相交则矢量叉积异号或为零，大于零则不相交
//        if ((((l1x1 - l2x1) * (l2y2 - l2y1) - (l1y1 - l2y1) * (l2x2 - l2x1)) 
//              * ((l1x2 - l2x1) * (l2y2 - l2y1) - (l1y2 - l2y1) * (l2x2 - l2x1))) > 0
//            || (((l2x1 - l1x1) * (l1y2 - l1y1) - (l2y1 - l1y1) * (l1x2 - l1x1)) 
//              * ((l2x2 - l1x1) * (l1y2 - l1y1) - (l2y2 - l1y1) * (l1x2 - l1x1))) > 0)
//        {
//            return false;
//        }
//        return true;
    }
	
	
	/**
	 * 线条与矩形有哪些边相交
	 * @param line	线条对象
	 * @param rect	矩形对象
	 * @return 获取矩形相交的有哪些边数组（1右，2上，3左，4下）
	 */
	public static byte[] getLineIntersectRectangleSide(Line line, Rectangle rect) {
		byte sideIndex = 0;
		byte [] sides = new byte[4];
		
		Line right = new Line(rect.getRightBottom().getX() ,rect.getLeftTop().getY() , rect.getRightBottom().getX() , rect.getRightBottom().getY());
		Line up = new Line(rect.getLeftTop().getX() ,rect.getLeftTop().getY() , rect.getRightBottom().getX() , rect.getLeftTop().getY());
		Line left = new Line(rect.getLeftTop().getX() ,rect.getLeftTop().getY() , rect.getLeftTop().getX() , rect.getRightBottom().getY());
		Line down = new Line(rect.getLeftTop().getX() ,rect.getRightBottom().getY() , rect.getRightBottom().getX() , rect.getRightBottom().getY());
		
		if(isLineIntersectionLine(line , right))
			sides[sideIndex++] = 1;
		
		if(isLineIntersectionLine(line , up))
			sides[sideIndex++] = 2;
		
		if(isLineIntersectionLine(line , left))
			sides[sideIndex++] = 3;
		
		if(isLineIntersectionLine(line , down))
			sides[sideIndex++] = 4;
		
		byte [] newSides = null;
		if(sideIndex == sides.length) {
			newSides = sides;
		}
		else {
			newSides = new byte[sideIndex];
			for (int i = 0; i < newSides.length; i++) 
				newSides[i] = sides[i];
		}
		return newSides;
    }
	/**
	 * 线条与矩形是否相交
	 * @param line	线条对象
	 * @param rect	矩形对象
	 * @return 返回是否与矩形相交
	 */
    public static boolean isLineIntersectRectangle(Line line, Rectangle rect) {
    	double linePointX1 = line.getLeftTop().getX();
    	double linePointY1 = line.getLeftTop().getY();
		double linePointX2 = line.getRightBottom().getX();
		double linePointY2 = line.getRightBottom().getY();
		
		double rectangleLeftTopX = rect.getLeftTop().getX();
		double rectangleLeftTopY = rect.getLeftTop().getY();
		double rectangleRightBottomX = rect.getRightBottom().getX();
		double rectangleRightBottomY = rect.getRightBottom().getY();
		
		
		double lineHeight = linePointY1 - linePointY2;
        double lineWidth = linePointX2 - linePointX1;  
        double t1 = lineHeight * rectangleLeftTopX + lineWidth * rectangleLeftTopY;
        double t2 = lineHeight * rectangleRightBottomX + lineWidth * rectangleRightBottomY;
        double t3 = lineHeight * rectangleLeftTopX + lineWidth * rectangleRightBottomY;
        double t4 = lineHeight * rectangleRightBottomX + lineWidth * rectangleLeftTopY;
        double c = linePointX1 * linePointY2 - linePointX2 * linePointY1;
        
        if(((t1 + c >= 0 && t2 + c <= 0) || (t1 + c <= 0 && t2 + c >= 0) || (t3 + c >= 0 && t4 + c <= 0) || (t3 + c <= 0 && t4 + c >= 0))) {
            if (rectangleLeftTopX > rectangleRightBottomX) {
                double temp = rectangleLeftTopX;
                rectangleLeftTopX = rectangleRightBottomX;
                rectangleRightBottomX = temp;
            }
 
            if (rectangleLeftTopY < rectangleRightBottomY) {
                double temp1 = rectangleLeftTopY;
                rectangleLeftTopY = rectangleRightBottomY;
                rectangleRightBottomY = temp1;
            }
 
            if ((linePointX1 < rectangleLeftTopX && linePointX2 < rectangleLeftTopX) || (linePointX1 > rectangleRightBottomX && linePointX2 > rectangleRightBottomX)
                    || (linePointY1 > rectangleLeftTopY && linePointY2 > rectangleLeftTopY) || (linePointY1 < rectangleRightBottomY && linePointY2 < rectangleRightBottomY)) {
                return false;
            } else {
                return true;
            }
        } else {
            return false;
        }
    }
    
    public static List<Rectangle> testLineIntersectRectangle() {
    	int startX = 19;
    	int startY = 10;
    	int endX = 15;
    	int endY = 13;
    	
    	int minX = Math.min(startX, endX);
    	int maxX = Math.max(startX, endX);
    	int minY = Math.min(startY, endY);
    	int maxY = Math.max(startY, endY);
    	Line line = new Line(startX, startY, endX, endY);
    	List<Rectangle> rectList = new ArrayList<Rectangle>();
    	
//    	for (int i = minX; i <= maxX; i++) 
//    	{
//    		for (int j = minY; j <= maxY; j++) 
//    		{
//    			Rectangle newRect = new Rectangle(i, j+1, i+1, j);
//				boolean inter = isLineIntersectRectangle(line , newRect);
//				if(inter)
//					rectList.add(newRect);
//			}
//    		LogTools.printOutLog("");
//		}
    	return rectList;
    }
	
	private static void testSector() {
		int width = 10, height = 10;
		String[][] map = new String[width][height];
		for (int i = 0; i < height; i++)
			for (int j = 0; j < width; j++)
				map[i][j] = "o ";

		Point role = new Point(2, 7);
		Point target = new Point(9, 0);

//		double angle = 30;
//		double targetAngle = getAngle(role, target);
//		double halfAngle = angle / 2;
//		double minAngle = targetAngle - halfAngle;
//		double maxAngle = targetAngle + halfAngle;
//		for (int i = 0; i < height; i++) {
//			for (int j = 0; j < width; j++) {
//				boolean is = isInSector(role, new Point(i, j), minAngle, maxAngle);
//				if (is) // true，则是在该扇形内
//					map[j][i] = "* ";
//			}
//		}
//		// 打印
//		for (int i = 0; i < height; i++) {
//			for (int j = 0; j < width; j++)
//				System.out.print(map[i][j]);
//			LogTools.printOutLog("");
//		}
	}


	private static void testgetLineIntersectRectangleSide() {
		Line line = new  Line(12, 19, 14, 15);
		Rectangle newRect = new Rectangle(14-0.5f, 16+0.5f, 14+0.5f, 16-0.5f);
		getLineIntersectRectangleSide(line, newRect);
	}
	
	
	public static void main(String[] args) {
//		testLineIntersectRectangle();
		testgetLineIntersectRectangleSide();
		
		
		
//		testSector();
		
//		boolean in = isLineIntersectRectangle(new Line(new Point(0, 0), new Point(2 ,9)) , new Rectangle(new Point(1, 4), new Point(8, 5)));
//		LogPrintTools.printOutLog(in);
		
//	    // 测试一个点是否在多边形内  
//	    Point point = new Point(8 ,5);  
//	    List<Point> pts = new ArrayList<Point>();  
//	    pts.add(new Point(4, 2));  
//	    pts.add(new Point(2, 4));  
//	    pts.add(new Point(4, 6));  
//	    pts.add(new Point(4, 9));
//	    pts.add(new Point(6, 9));
//	    pts.add(new Point(8, 5));
//	    pts.add(new Point(7, 2));
//	       
//	    if(isInPtInPoly(point, pts))
//	      LogPrintTools.printOutLog("点在多边形内");
//	    else
//	      LogPrintTools.printOutLog("点在多边形外");

//	    // 测试一个点是否在圆形内  
//	    Point centerPoint = new Point(7, 6);  
//	    Circle c = new Circle(new Point(10,10) , 5); 
//	    String s = isInCircle(centerPoint,c); 
//	    LogPrintTools.printOutLog("点是否在圆内："+s);
	}

}
